<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>最长回文子序列</title>
  </head>

  <body>
    <script>
      //  将字符串反转 求最长公共子序列
      // 动态规划
      /* 

         // 确定遍历顺序

             a c b a      i
          a  1 1 1 3 
          c    1 1 1 
          b      1 1     
          a        1 
                    
         
          j
       b  b  b  a  b      
  b   [1, 2, 3, 3, 4]
  b   [0, 1, 2, 2, 3]
  b   [0, 0, 1, 1, 3]
  a   [0, 0, 0, 1, 1]
  b   [0, 0, 0, 0, 1]
         
        
        */
      const longestPalindromeSubseq = (s) => {
        const strLen = s.length;
        let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));

        for (let i = 0; i < strLen; i++) {
          dp[i][i] = 1;
        }

        for (let i = strLen - 1; i >= 0; i--) {
          for (let j = i + 1; j < strLen; j++) {
            if (s[i] === s[j]) {
              dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
              dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
          }
        }
        console.log(dp);

        return dp[0][strLen - 1];
      };

      console.log(longestPalindromeSubseq("bbbab"));
    </script>
  </body>
</html>
